package io.github.handyang.algorithms.search;


import java.util.ArrayList;
import java.util.List;

public class BinarySearchST<K extends Comparable<K>, V> implements SymbolTable<K, V> {
    private Node[] data;

    private int size;

    public BinarySearchST() {
        clear();
    }

    @Override
    public void put(K key, V value) {
        reSize();

        int i = 0;
        for (i = 0; i < size(); i++) {
            int compare = data[i].key.compareTo(key);
            if (compare == 0) {
                data[i].value = value;
                return;
            } else if (compare > 0) {
                //i 的key 小于 k
                break;
            }
        }

        if (i < size()) {
            //插入数组
            for (int j = size(); j > i; j--) {
                data[j] = data[j - 1];
            }
        }

        data[i] = new Node(key, value);
        this.size++;
    }

    @Override
    public V get(K key) {
        int lo = 0, hi = size() - 1;

        while (lo < hi) {
            int mid = ((hi - lo) >> 1) + lo;

            int compare = data[mid].key.compareTo(key);
            if (compare == 0) return (V) data[mid].value;
            else if (compare > 0) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }

        if (lo < size() && data[lo].value != null && data[lo].key.equals(key)) return (V) data[lo].value;

        return null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterable<K> keys() {
        List<K> keys = new ArrayList<>();

        for (int i = 0; i < size(); i++) {
            if (data[i].value != null) {
                keys.add((K) data[i].key);
            }
        }

        return keys;
    }

    @Override
    public void clear() {
        this.data = new Node[16];
        this.size = 0;
    }

    private void reSize() {
        if (this.size() != this.data.length) {
            return;
        }

        Node[] newData = new Node[this.data.length << 1];
        System.arraycopy(data, 0, newData, 0, data.length);

        this.data = newData;
    }

    private static final class Node<K extends Comparable<K>, V> {
        private K key;
        private V value;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
